package com.tedu.bill;
/*
* 使用递归完成斐波那契
*
* 1  1   2  3  5  8  13  21  34  55 ...
* factorial(n) = factorial(n-1) + factorial(n-2)
* factorial(3) = factorial(2) + factorial(1)
*              =  1　+ 1
*              = 2
* factorial(4) = factorial(4-1) + factorail(4-2)
*              = factorial(3) + factorail(2)
*              = factorial(2) + factorial(1) + factorail(2)
*              = 2* factorial(2) + factorial(1)
*              = 2 * 1 +1
*              = 3
*
* */
public class TestFactorial1 {
    public static void main(String[] args) {
        //打印10位的斐波拉契
        for (int i = 1; i <= 20; i++) {
            System.out.print( factorial( i ) + "  " );
        }
        System.out.println("........");
    }
    //完成斐波拉契的功能
    //n表示的是第几个数字
    public static int factorial(int n){
        //最终的出口条件是
        if( n == 1 || n == 2) return  1;
        //第n位上的数字等于第n-1上的数字 加 第n-2上的数字和
        return factorial(n-1)+factorial(n-2);
    }
}
